The present invention relates to data networking and more particularly to distribution of routing information in the Internet.
Packets travel from their origin to their destination through a series of routers. The route is not generally predetermined but rather selected hop-by-hop based on the destination network address. A forwarding table at each router correlates destination address information to next-hops. Internet routing protocols concern themselves with appropriately populating the contents of such forwarding tables.
For routing purposes, the Internet may be considered to be divided into Autonomous Systems (ASs) where each AS is a group of networks and routers under common administrative control. The routing of packets within an AS is addressed by an intradomain protocol or interior gateway protocol (IGP) operative within that AS. There are several different available IGPs including OSPF, RIP, etc. Routing of packets across AS boundaries is controlled by an interdomain routing protocol. The current prevalent interdomain routing protocol is BGP and is described in, e.g., Rekhter, et al. “A Border Gateway Protocol 4 BGP-4,” RFC 1771, Internet Engineering Task Force, March 1995 the contents of which are herein incorporated by reference in their entirety.
A single BGP session involves two nodes and involves an exchange of routing information via a point-to-point TCP connection. For example, one node will tell the other node, e.g., that a particular route is available to a particular network or that a previously advertised route is no longer available. Destination networks are identified by prefixes, i.e., a combination of destination network address and bit mask to be used in matching packet addresses to the network address. A particular unit of route information may be referred to herein as a “path.” A path identifies 1) a destination network address (prefix), 2) a list of AS's traversed by the BGP message containing the path on its way to the BGP listener, and 3) a next-hop address, i.e., an address of a border router within the AS of the BGP listener that may be used to reach the destination network address. Nodes receiving BGP route updates will use the information to update their own forwarding tables and to propagate the route updates further. A node receiving multiple paths to the same destination network will generally pick one or more for its forwarding table and to distribute to other nodes via BGP. In this manner, information about how to route packets across AS boundaries is propagated across the Internet.
Different variants of BGP communication are used depending on whether the route information is itself being distributed across AS boundaries or within an AS. External BGP (EBGP) is used to distribute route information across AS boundaries while Internal BGP (IBGP) is used to distribute route information within an AS. Again, for both kinds of BGP, the route information concerns how to route payload packets across AS boundaries.
In practice, border routers at the borders of an AS will use EBGP to communicate paths with other AS's and IBGP to distribute the route information they have learned within their own AS. The message structure and types of information communicated are highly similar. However, EBGP and IBGP have different rules for advertising paths. In particular, a border router that learns about a path via EBGP may advertise this path via either EBGP or IBGP. A path that is learned via IBGP cannot, however, be advertised to another node via IBGP. This is done to avoid routing update loops. BGP's method for avoiding routing loops is to track the AS boundaries that are crossed. This does not work within an AS so information learned via IBGP is not readvertised.
A consequence of this rule is that the basic IBGP protocols rely on a full mesh of BGP sessions between each border router and each router in the AS interior. This approach suffers from serious scalability problems. The number of TCP connections from each router grows linearly with the number of routers in the AS. An additional drawback is that multiple IBGP connections from a BR to internal routers may traverse the same link forcing identical information to be carried as many times over the link.
Because of these problems, alternate approaches have been developed. One such approach is to add hierarchy by employing route reflection. Some nodes in the AS act as route reflectors. A route reflector has assigned client routers and readvertises routes it hears from non-clients to clients and routes it hears from clients to non-clients. Deploying route reflectors solves the “full mesh” scalability problems at the expense of possible routing information inconsistency, additional convergence delay and introduction of artificial failure points.
Route reflectors use IBGP connections to communicate with their clients. The route reflectors only propagate a single path for each destination network from the options available to them. The selection made by the route reflector on behalf of its clients hides information and may result in forwarding as well as routing update loops. Ongoing work is adding the capability of conveying multiple viable paths through IBGP in an attempt to solve these problems.
Route reflectors also affect the speed of propagation of BGP routing information through the AS. A route reflector reuses much of the mechanism of a regular BGP speaker and operates as follows:                1. The route reflector receives viable paths from a number of AS BRs (or other route reflectors if multiple levels of reflector hierarchy are used).        2. It runs a BGP best path algorithm to calculate the winning path for each destination network.        3. It propagates the winning path to its clients.        
The three steps in the above process can take a variable amount of time, depending on the BGP implementation. The total delay for a route reflector to propagate a route can be significant. The delay introduced by route reflectors clearly does not exist in the “full mesh” IBGP solution as border routers propagate information in parallel to all other AS routers.
An additional problem of route reflectors is that they introduce an artificial point of failure. A route reflector conveys to its clients paths to remote destinations through AS border routers. When the route reflector fails, a client no longer receives paths. However, the route reflector failure does not mean that the client has lost the ability to forward data towards the border router. In fact even if the route reflector was on the forwarding path between the client and the border router, the IGP operated by the AS may converge on an alternative internal path. Hence, the route reflector failure disables the client although network connectivity still exists. A deployment workaround is to configure the network so that internal routers are always clients of more than one route reflector. As long as one of the route reflectors serving a client is functional, the client will receive BGP information. The drawback is that now the client has to receive process and store redundant information from each of the multiple route reflectors.
An alternative approach is to, instead of imposing a routing information distribution hierarchy, rather divide the AS into “confederations”. IBGP is then used within each confederation while a variant of EBGP is used between confederations. The use of confederations causes problems similar to those caused by the use of route reflectors.
Improved systems and methods for distributing interdomain routing information within an AS are thus needed. Improvements are needed that will simultaneously provide scalability, efficient use of processor and memory resources, avoidance of forwarding loops, consistency of routing information across the AS, improved speed of network convergence, etc.